package com.atguigu.kruskal;

import java.util.Arrays;

public class KruskalCase {

	private int edgeNum; //??????
	private char[] vertexs; //????????
	private int[][] matrix; //??????
	//??? INF ????????????????
	private static final int INF = Integer.MAX_VALUE;
	
	public static void main(String[] args) {
		char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
		//??????????????????  
	      int matrix[][] = {
	      /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
	/*A*/ {   0,  12, INF, INF, INF,  16,  14},
	/*B*/ {  12,   0,  10, INF, INF,   7, INF},
	/*C*/ { INF,  10,   0,   3,   5,   6, INF},
	/*D*/ { INF, INF,   3,   0,   4, INF, INF},
	/*E*/ { INF, INF,   5,   4,   0,   2,   8},
	/*F*/ {  16,   7,   6, INF,   2,   0,   9},
	/*G*/ {  14, INF, INF, INF,   8,   9,   0}}; 
	      //?????????????????????????????????????С??????.
	      
	      //????KruskalCase ???????
	      KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);
	      //?????????
	      kruskalCase.print();
	      kruskalCase.kruskal();
	}
	
	//??????
	public KruskalCase(char[] vertexs, int[][] matrix) {
		//??????????????????
		int vlen = vertexs.length;
		
		//?????????, ???????????
		this.vertexs = new char[vlen];
		for(int i = 0; i < vertexs.length; i++) {
			this.vertexs[i] = vertexs[i];
		}
		
		//???????, ????????????????
		this.matrix = new int[vlen][vlen];
		for(int i = 0; i < vlen; i++) {
			for(int j= 0; j < vlen; j++) {
				this.matrix[i][j] = matrix[i][j];
			}
		}
		//?????????
		for(int i =0; i < vlen; i++) {
			for(int j = i+1; j < vlen; j++) {
				if(this.matrix[i][j] != INF) {
					edgeNum++;
				}
			}
		}
		
	}
	public void kruskal() {
		int index = 0; //?????????????????
		int[] ends = new int[edgeNum]; //???????"??????С??????" ?е????????????С???????е????
		//???????????, ??????????С??????
		EData[] rets = new EData[edgeNum];
		
		//?????? ???е?????? ?? ?????12??
		EData[] edges = getEdges();
		System.out.println("????????=" + Arrays.toString(edges) + " ??"+ edges.length); //12
		
		//??????????С????????(??С????)
		sortEdges(edges);
		
		//????edges ???飬??????????С????????????ж??????????????γ????·???????У?????? rets, ?????????
		for(int i=0; i < edgeNum; i++) {
			//???????i?????????????(???)
			int p1 = getPosition(edges[i].start); //p1=4
			//???????i??????2??????
			int p2 = getPosition(edges[i].end); //p2 = 5
			
			//???p1???????????????С???????е????
			int m = getEnd(ends, p1); //m = 4
			//???p2???????????????С???????е????
			int n = getEnd(ends, p2); // n = 5
			//?????·
			if(m != n) { //??й????·
				ends[m] = n; // ????m ??"??????С??????"?е???? <E,F> [0,0,0,0,5,0,0,0,0,0,0,0]
				rets[index++] = edges[i]; //??????????rets????
			}
		}
		//<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>??
		//??????? "??С??????", ???  rets
		System.out.println("??С???????");
		for(int i = 0; i < index; i++) {
			System.out.println(rets[i]);
		}
		
		
	}
	
	//?????????
	public void print() {
		System.out.println("???????: \n");
		for(int i = 0; i < vertexs.length; i++) {
			for(int j=0; j < vertexs.length; j++) {
				System.out.printf("%12d", matrix[i][j]);
			}
			System.out.println();//????

		}
	}

	/**
	 * ?????????????????, ???????
	 * @param edges ??????
	 */
	private void sortEdges(EData[] edges) {
		for(int i = 0; i < edges.length - 1; i++) {
			for(int j = 0; j < edges.length - 1 - i; j++) {
				if(edges[j].weight > edges[j+1].weight) {//????
					EData tmp = edges[j];
					edges[j] = edges[j+1];
					edges[j+1] = tmp;
				}
			}
 		}
	}
	/**
	 * 
	 * @param ch ????????????'A','B'
	 * @return ????ch?????????±???????????????-1
	 */
	private int getPosition(char ch) {
		for(int i = 0; i < vertexs.length; i++) {
			if(vertexs[i] == ch) {//???
				return i;
			}
		}
		//?????,????-1
		return -1;
	}
	/**
	 * ????: ?????б?????EData[] ?????У??????????????????????
	 * ?????matrix ???????????
	 * EData[] ??? [['A','B', 12], ['B','F',7], .....]
	 * @return
	 */
	private EData[] getEdges() {
		int index = 0;
		EData[] edges = new EData[edgeNum];
		for(int i = 0; i < vertexs.length; i++) {
			for(int j=i+1; j <vertexs.length; j++) {
				if(matrix[i][j] != INF) {
					edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);
				}
			}
		}
		return edges;
	}
	/**
	 * ????: ????±??i?????????(), ????????ж???????????????????
	 * @param ends ?? ??????????????????????????????,ends ????????????????У????γ?
	 * @param i : ????????????????±?
	 * @return ???????? ?±??i??????????????????±?, ??????????????
	 */
	private int getEnd(int[] ends, int i) { // i = 4 [0,0,0,0,5,0,0,0,0,0,0,0]
		while(ends[i] != 0) {
			i = ends[i];
		}
		return i;
	}
 
}

//?????????EData ?????????????????????
class EData {
	char start; //????????
	char end; //????????????
	int weight; //?????
	//??????
	public EData(char start, char end, int weight) {
		this.start = start;
		this.end = end;
		this.weight = weight;
	}
	//??дtoString, ????????????
	@Override
	public String toString() {
		return "EData [<" + start + ", " + end + ">= " + weight + "]";
	}
	
	
}
